#include <vector>
using namespace std;

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            // 先计算平方值
            nums[i] = nums[i] * nums[i];

        }
        // 记录最小的元素
        int mind = nums[0], mini = 0;
        // 寻找最小的元素
        for (int i = 1; i < n; i++)
        {
            // 如果说当前遍历到的值比当前所记录的最小值小，就更换mind的值
            if (nums[i] < mind)
            {
                mind = nums[i];
                // 当前最小值的索引
                mini = i;
            }
            
        }
        vector<int> ans(n, 0);
        // 累计归并的元素的个数
        int k = 0;
        ans[k++] = mind;
        // 二路归并
        int i = mini - 1, j = mini + 1;
        while (i >= 0 && j < n)
        {
            if (nums[i] <= nums[j])
            {
                ans[k] = nums[i];
                // 指针向左移动
                i--;
                k++;
            }else{
                ans[k] = nums[j];
                // 指针向右移动
                j++;
                k++;
            }
            
        }
        // 左边的序列没有归并完毕时
        while (i >= 0)
        {
            ans[k] = nums[i];
            i --, k++;
        }
        while (j < n)
        {
            ans[k] = nums[j];
            j++, k++;
        }
        
        return ans;
    }
};

int main(){

    return 0;
}